package paper.cluster;

import java.sql.*;
import java.awt.Color;

import java.io.PrintWriter;
import java.io.FileWriter;
import java.io.IOException;

import java.util.HashSet;
import java.util.TreeSet;
import java.util.Set;
import java.util.Date;
import java.util.Random;
import java.util.Iterator;
import java.util.Vector;

import paper.db.DB;
import paper.db.Paper;
import paper.db.PaperIndex;
import paper.graph.PaperGraph;
import paper.graph.Vertex;



/* An EdgeTree is a breadth-first traversal of the edges in a
   PaperGraph, rooted at one particular edge. For simplicity
   the edges from the graph are stored as tree edges rather
   than as vertices. This representation means that vertices in
   the tree are Papers with the extra constraint that no edge
   exists twice. This is equivalent to ensuring unique vertices
   under breadth-first search. All papers are stored as Strings 
   of keys.
*/
class EdgeTree
{
    HashSet<String> papers;
    PaperGraph graph;       // Ugly but correct?
    int loop;
    int number;
    class ETree {
        int depth;
        ETree[] children;
        String node;

        ETree( String key, int d)
        {
            node = key;
            depth = d;
            children = null;
        }

        void deepen(int bound)
        {
            if(loop!=-1 && depth+2>loop)
                return;
            int i;
//            System.out.print("Tree " + depth + ": " + node + " ");
            if(depth>bound) {
//                System.out.println("- done");
                return;
            }
            if(children==null)
            {
                Set<String> adj = new HashSet<String>(graph.getNeighbours(node));
//                for( String s : adj )
//                    System.out.print(s + " ");
                if( adj.contains( subrootKey ) && !node.equals(rootKey))
                {
                    if( loop==-1 ) {
                        loop = depth+2;
                        number=1;
                    }
                    else
                        number++;
                }
                adj.removeAll( papers );
//                System.out.println("");
//                for(String s : adj )
//                    System.out.print(s + " ");
//                System.out.println("");
                children = new ETree[ adj.size() ];
                i=0;
                for( String key : adj )
                {
//                    System.out.println("Child " + i + " key");
                    children[i++] = new ETree( key, depth+1 );
                    papers.add( key );
                }
            }

            if( children.length==0 )
                return;

            if( loop==-1 )
                for(i=0; i<children.length; i++)
                    children[i].deepen(bound);
        }

        void dump()
        {
            for(int i=0; i<depth; i++)
                System.out.print("  ");
            System.out.println(node);
            if(children!=null)
                for(int i=0; i<children.length; i++)
                    children[i].dump();
        }
    }
    ETree root;
    // The EdgeTree rooted on a->b has b as the root (first
    // vertex in the tree) and a as the subroot.
    String subrootKey,rootKey;

    // Construct the tree rooted at the graph edge a->b
    EdgeTree(String a, String b, PaperGraph g)
    {
        rootKey = a;
        subrootKey = b;
        root = new ETree(rootKey,0);
        papers = new HashSet<String>();
        papers.add(rootKey);
        papers.add(subrootKey);
        graph = g;
        loop = -1;
        number = 1;
    }

    /* Perform breadth first search by iterative deepening */
    void deepen(int bound)
    {
        for(int i=0; i<=bound; i++)
            root.deepen(i);
        //System.out.println("EdgeTree("+rootKey+","+subrootKey+")");
        //root.dump();
    }

    /*HashSet<Paper> iterativeDeepen(int bound)
    {
        for( int i=1; i<=bound; i++)
        {
            HashSet<Paper> result = addLevel(i);
            if( result!= null )
                return result;
        }
        return null;
    }

    HashSet<Paper> addLevel(int n)
    {
        HashSet<Paper> result;
        if(n<=0)
            return null;
        if( children==null )
        {
            children = new EdgeTree[ root.cocites.size() ];
            int cnt=0;
            for(Iterator<Paper> i=root.cocites.iterator(); 
                i.hasNext(); )
            {
                Paper np = i.next();
                if( !parents.contains(np) )
                {
                    if( depth>0 && np==target )
                    {
                        result = new HashSet<Paper>(parents);
                        result.add(np);
                        return result;
                    }
                    children[cnt++] = new EdgeTree( np, this);
                }
            }
        }
        for(int i=0; i<children.length; i++)
        {
            if( children[i]!=null )
            {
                result = children[i].addLevel(n-1);
                if( result!=null )
                    return result;  
            }
        }
        return null;
    }*/

}

public class Cluster 
{
/*
    public void localGraph(Paper p, int n)
    {
        if( n<0 || p.mark>0)
            return;
        p.mark = 1;
        p.getCocitations();
        System.out.println("localGraph("+n+"): " + p);
        for(Iterator<Paper> i=p.cocites.iterator(); i.hasNext(); )
        {
            localGraph( i.next(), n-1) ;
        }
    }

    public Cluster() throws IOException
    {
        PaperIndex cache = new PaperIndex();
        Paper start = Paper.loadOnKey("1dfc3abf8adffd53", cache);

        cache.clearMarks();
        localGraph(start,1);
        HashSet<Paper> subgraph = cache.getMarked(1);

        PrintWriter out = new PrintWriter(new FileWriter( "cocite.dot" ));
        out.println("digraph{");
        dot( out, subgraph, start, null );
        out.println("}");

        for(Iterator<Paper> i=start.cocites.iterator(); i.hasNext(); )
        {
            Paper first = i.next();
            EdgeTree e = new EdgeTree(first,start);
            HashSet<Paper> cycle = e.iterativeDeepen(10);
            out.println("digraph{");
            for(Iterator<Paper> j=subgraph.iterator(); j.hasNext(); )
                j.next().mark=1;
            dotCycle( out, subgraph, start, null, cycle );
            out.println("}");
        }
        out.close();

    }

    public void dotCycle(PrintWriter out, HashSet<Paper> set, Paper p, 
                         Paper cut, HashSet<Paper> cycle)
    {
        if( p.mark!=1 )
            return;
        p.mark=0;
        if( p!=cut )
        {
            if( cycle.contains(p) )
                out.println("x"+p.key + " [color=red,label=\"" + p.title.replace('\n',' ').replace('"','!') + "\"];");
            else
                out.println("x"+p.key + " [label=\"" + p.title.replace('\n',' ').replace('"','!') + "\"];");
        }
        for(Iterator<Paper> i=p.cocites.iterator(); i.hasNext(); )
        {
            Paper t = i.next();
            if( t != null )         // Why the fuck is t null sometimes?
            {
                if( set.contains(t) && 
                    String.CASE_INSENSITIVE_ORDER.compare(p.key,t.key)<0 
                    && t!=cut && p!=cut) 
                {
                    if( cycle.contains(p) && cycle.contains(t) )
                        out.println("x"+p.key + " -> " + "x"+t.key + " [dir=none,color=red];");
                    else
                        out.println("x"+p.key + " -> " + "x"+t.key + " [dir=none];");
                }
                if( t.mark == 1 )
                    dotCycle( out, set, t, cut, cycle);
            }
        }
    }

    public void dot(PrintWriter out, HashSet<Paper> set, Paper p, Paper cut)
    {
        if( p.mark!=1 )
            return;
        p.mark=0;
        if( p!=cut )
            out.println("x"+p.key + " [label=\"" + p.title.replace('\n',' ').replace('"','!') + "\"];");
        for(Iterator<Paper> i=p.cocites.iterator(); i.hasNext(); )
        {
            Paper t = i.next();
            if( t != null )         // Why the fuck is t null sometimes?
            {
                if( set.contains(t) && 
                    String.CASE_INSENSITIVE_ORDER.compare(p.key,t.key)<0 
                    && t!=cut && p!=cut) 
                    out.println("x"+p.key + " -> " + "x"+t.key + " [dir=none];");
                if( t.mark == 1 )
                    dot( out, set, t, cut);
            }
        }
    }

    public void buildCociteGraph(Paper p)
    {
        for(Iterator<Paper> i=p.cocites.iterator(); i.hasNext(); )
        {
            Paper nxt = i.next();
            if( nxt.mark == 0)
            {
                nxt.getCocitations();
                nxt.mark = -1;
            }
        }
        for(Iterator<Paper> i=p.cocites.iterator(); i.hasNext(); )
        {
            Paper nxt = i.next();
            if( nxt.mark == -1)
            {
                nxt.mark = p.mark+1;
                buildCociteGraph( nxt );
            }
        }
    }

*/
    public static void minLoops( PrintWriter out, PaperGraph<CEdge,Vertex> g )
    {
        // First compute the mincycle measure for each edge
        for( CEdge e : g.edgeSet() )
        {
            EdgeTree et = new EdgeTree( e.keyA, e.keyB, g ); 
            et.deepen( 10 );
            e.m.length = et.loop;
            e.m.number = et.number;
        }
        // Construct a ranking of the values in the measure.
        // The ordering used is lexographic, firstly on the
        // cycle length (small-large), then on the number of 
        // paths (large-small).
        TreeSet<CEdge.Measure> ms = new TreeSet<CEdge.Measure>();
        for( CEdge e : g.edgeSet() )
            ms.add( e.m );
        // Using the measure ranks as boundaries in the graph
        // compute the connected subgraphs
        for( CEdge.Measure m : ms )
        {
            System.out.println("M: " + m);
            PaperGraph<CEdge,Vertex> copy = new PaperGraph<CEdge,Vertex>(g);
            for( Vertex v : copy.vertices.values() )
                v.colour = Color.RED;

            for( CEdge e : copy.edgeSet() )
            {
                if( e.m.compareTo( m ) <= 0 )
                {
                    Vertex vA = copy.vertices.get( e.keyA );
                    Vertex vB = copy.vertices.get( e.keyB );
                    //System.out.println("Edge " + e + " (" +
                    // e.keyA + "," + e.keyB + ") " + vA + " " + vB);
                    vA.colour = Color.GREEN;
                    vB.colour = Color.GREEN;
                }
            }

            for( CEdge e : copy.edgeSet() )
            {
                Vertex vA = copy.vertices.get( e.keyA );
                Vertex vB = copy.vertices.get( e.keyB );
                if( vA.colour == Color.GREEN &&
                    vB.colour == Color.GREEN)
                    e.col = Color.GREEN;
                else
                if( vA.colour != Color.GREEN &&
                    vB.colour != Color.GREEN)
                    e.col = Color.RED;
                else
                    e.col = Color.BLUE;
            }
            //copy.dump();
            copy.dot(out,true,false);
        }
    }

    public static void main(String[] args) throws IOException
    {
        PaperIndex index = new PaperIndex();
        PaperGraph<CEdge,Vertex> graph = new PaperGraph<CEdge,Vertex>( index );
        graph.fillGraph( "1dfc3abf8adffd53", 1, "cocitations", new CEdge("x","x"));
        //graph.dump();
        /*for( Edge e : graph.edgeSet() )
        {
            EdgeTree et = new EdgeTree( e.keyA, e.keyB, graph ); 
            et.deepen( 10 );
            e.number = et.loop;
            System.out.println(e);
        }*/
        //graph.dump();
        PrintWriter out = new PrintWriter(new FileWriter( "cites.dot" ));
        graph.dot( out,true,false );
        out.close();
    }

}
